51nod1067 Bash游戏 V2

传送门：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1067

Solution

打个表找规律。。。发现n为7的倍数或七的倍数余二则B赢，否则A赢。
证明：
设n=7(k+1)+b(b＜7)，k=0的情况可以手算出来。
b=0时，n=7(k+1)，若A选1，则B选4，此时剩余7k+2，B胜；若A选3/4，则B选4/3，剩余7k，B胜。
b=1/3/4时，n=7(k+1)+1/3/4，A选1/3/4，剩余7(k+1)，A胜。
b=2时，n=7(k+1)+2,若A选1，则B选1，剩余7(k+1)，B胜；若A选择3/4，则B选4/3，剩余7k+2，B胜。
b=5/6时，n=7(k+1)+5/6，A选3/4，剩余7(k+1)+2，A胜。
k可以一直往后推所以结论成立。

Code

#include<cstdio>
#include<cstring>
int T,n;
int main(){
/*  int f[1000]; memset(f,0,sizeof f);
    for (int i=1;i<=1000;i++){
        f[i]=f[i]||!f[i-1];
        if (i-3>=0) f[i]=f[i]||!f[i-3];
        if (i-4>=0) f[i]=f[i]||!f[i-4];
    }
    for (int i=1;i<=30;i++)
        printf("%d ",f[i]);*/
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n); n%=7;
        if (!n||n==2) putchar('B');
        else putchar('A');
        putchar('\n');
    }
}